<?php
/**
 *对一个数组内的元素实现翻转
 *
 *@param array $array 目标数组
 *@return 返回翻转之后的数组
 */

/******************************************************************/

function reverse($array)
{
	$n = count($array);
	for ($i=0; $i<$n/2; $i++) {
		$temp = $array[$i];
		$array[$i] = $array[$n - $i -1];
		$array[$n - $i -1] = $temp;
	}
	return $array;
}

/******************************************************************/

/**
 *把新元素插入给定数组的指定位置
 *
 *@param array $array 按引用传递的数组
 *@param integer $position 制定要插入新元素的位置
 *@param $element 要插入的新元素
 *@return ture表示插入成功，false表示插入失败
 */

function insert(&$array, $position, $element)
{
	$n = count($array);
    if (($position < 0) || ($position > $n - 1)) {
        echo '要插入的下标位置必须在0~' . $n;
        return false;
    }
    for ($i=$n - 1; $i>=$position; $i--) {
    	$array[$i + 1] = $array[$i];
    }
    $array[$position] = $element;
    return true;
}

/******************************************************************/

/**
 *插入排序
 *
 *@param array $array 排序的目标数组
 *@return 返回排好序的数组
 */

function insert_sort($array)
{
	$sortArr = [];
	//取出一个数
	for ($i=0; $i<count($array); $i++) { 
		$temp = $array[$i];
		//判断这个数的大小和位置
		for ($j=0; $j<$i; $j++) {
			if ($i > 0) {
				if ($temp < $sortArr[$j]) {
					//插入这个数
					insert($sortArr, $j, $temp);
					$sortArr[$j] = $temp;
					break;
				}
				if ($temp > $sortArr[$i-1]) {
					$sortArr[$i] = $temp;
					break;
				}
			}
		}
		if ($i == 0){
			$sortArr[0] = $array[0];
		}
	}
	return $sortArr;
}

/******************************************************************/

/**
 *二分查找
 *
 *@param array $array 目标数组
 *@param integer $target 目标元素
 *@return 目标元素在所在数组中的下标
 */

function binary_search($array, $target)
{
	$start = 0;
	$end = count($array) - 1;
	$flag = -1;

	while ($start <= $end) {
		$mid = round(($end - $start) / 2 + $start);
		if ($array[$mid] == $target) {
			$flag = $mid;
			break;
		}elseif ($array[$mid] < $target) {
			$start = $mid + 1;
		}else $end = $mid - 1;
	}
	return $flag;
}